package codeRandomThoughts.Test93复原IP地址;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    List<String> result = new ArrayList<>();
    StringBuilder path = new StringBuilder();
    int countDot = 0;

    public List<String> restoreIpAddresses(String s) {
        int startIndex = 0;
        char[] c = s.toCharArray();
        backtracking(c, startIndex);
        return result;
    }

    public void backtracking(char[] s, int startIndex) {
        //终止条件
        if (countDot > 3) {
            if (path.length() == s.length + 3) {
                result.add(new String(path));
            }
            return;
        }


        //单层搜索逻辑
        for (int i = startIndex; i < startIndex + 3 && i < s.length; i++) {
            char[] subChar = Arrays.copyOfRange(s, startIndex, i + 1);
            //检测ip地址是否有效
            if (isValid(subChar)) {
                //有效地址加入path中
                if (!path.isEmpty()) {
                    path.append('.');
                }
                path.append(subChar);
                countDot++;
                backtracking(s, i + 1);
                //回溯
                countDot--;
                path.delete(path.length() - subChar.length, path.length());
                //防止越界
                if (!path.isEmpty()) {
                    path.deleteCharAt(path.length() - 1);
                }
            }
        }
    }

    public boolean isValid(char[] subChar) {
        if (subChar.length > 1 && subChar[0] == '0') {
            return false;
        } else if (subChar.length > 3) {
            return false;
        }
        String tem = String.valueOf(subChar);

        if (String.valueOf(subChar).isEmpty()) {
            return false;
        } else if ( Double.parseDouble(String.valueOf(subChar)) > 255) {
            return false;
        }
        return true;
    }
}